#define _CRT_SECURE_NO_WARNINGS 1
typedef pair<string, int> PII;
bool cmp(string& a, string& b) {
    if (a.size() == b.size())return a < b;
    return a.size() < b.size();
}
class Solution {
public:
    vector<string> shortestSubstrings(vector<string>& arr) {
        unordered_map<string, int> mp;
        unordered_map<int, vector<string> >mp2;
        unordered_map<int, unordered_map<string, int>> mp3;
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            for (int len = 1; len <= arr[i].size(); len++) {
                for (int l = 0; l + len - 1 < arr[i].size(); l++) {
                    //int r=l+len-1;
                    string res = arr[i].substr(l, len);
                    mp[res]++;
                    mp2[i].push_back(res);
                    mp3[i][res]++;
                }
            }
            sort(mp2[i].begin(), mp2[i].end(), cmp);
        }
        vector<string> ans(n);
        for (int i = 0; i < n; i++) {
            for (auto it : mp2[i]) {
                if (mp3[i][it] == mp[it]) {
                    ans[i] = it;
                    break;
                }
            }
        }
        return ans;
    }
};